#pragma once
#include <map>
#include <limits>
#include <vector>
#include <list>
#include <stack>

using std::map;
using std::list;
using std::pair;
using std::vector;
using std::make_pair;

enum EColour{WHITE,GRAY,BLACK};

template <typename Name>
class BiGraph {
  public:
    class Vertex;
    class Edge;

    template <typename T, typename U>
    class Iterator{
      public:
        Iterator(T It):ptr(It) {};
        Iterator& operator++(){ptr++; return *this;}
        Iterator& operator--(){ptr--; return *this;}
        Iterator operator++(int){Iterator temp; temp.ptr=ptr; ptr++; return temp;}
        Iterator operator--(int){Iterator temp; temp.ptr=ptr; ptr--; return temp;}
        bool operator==(const Iterator& It) const {return (ptr==It.ptr);}
        bool operator!=(const Iterator& It) const {return (ptr!=It.ptr);}
        U& operator*(){ return *(ptr->second); }
        U* operator->(){ return ptr->second; }
        Iterator& operator=(const Iterator& It) {ptr=It.ptr; return *this;}

      private:
        T  ptr;
    };

    typedef typename map<Name,Vertex*>::iterator map_NV_It;
    typedef typename map<Vertex*, Edge*>::iterator map_VE_It;
    typedef Iterator< map_NV_It, Vertex > Vertex_Iterator;
    typedef Iterator< map_VE_It, Edge > In_Edge_Iterator;
    typedef Iterator< map_VE_It, Edge > Out_Edge_Iterator;

    typedef std::pair<Vertex_Iterator, Vertex_Iterator> Vertices_Range;

    class Edge{
        friend class BiGraph;
      public:
        Edge(Vertex* start, Vertex* end, double w):weight(w), start_vertex(start), end_vertex(end) {}
        pair<Name, Name> get_name() const { return make_pair(start_vertex->get_name(), end_vertex->get_name()); }
        pair<Vertex*,Vertex*> get_vertices() const { return make_pair(start_vertex, end_vertex); }
        double get_weight() const { return weight; }
        bool closed;
      private:
        double weight;
        Vertex* start_vertex;
        Vertex* end_vertex;
    };

    class Vertex{
        friend class BiGraph;
      public:
        Vertex(const Name &_name): colour(WHITE), name(_name) {}
        Vertex(): colour(WHITE) {};
        Name get_name() const { return name; }
        double cost;
        bool closed;
        EColour colour;
        Vertex* parent;

        In_Edge_Iterator in_edge_begin() { return In_Edge_Iterator(in_edges.begin()); }
        In_Edge_Iterator in_edge_end() { return In_Edge_Iterator(in_edges.end()); }

        Out_Edge_Iterator out_edge_begin() { return Out_Edge_Iterator(out_edges.begin()); }
        Out_Edge_Iterator out_edge_end() { return Out_Edge_Iterator(out_edges.end()); }

      private:
        Name name;
        map<Vertex*, Edge*> out_edges;
        map<Vertex*, Edge*> in_edges;
    };

    explicit BiGraph(bool o):edges_count(0), orient(o) {}
    BiGraph():edges_count(0), orient(true){}
    ~BiGraph(){ clear(); }
    void clear();

    Vertex_Iterator begin() { return Vertex_Iterator(vertices_map.begin()); }
    Vertex_Iterator end() { return Vertex_Iterator(vertices_map.end()); }

    pair<bool, Vertex*> add_vertex(const Name &v);
    Edge* add_edge(const Name &start, const Name & end, double weight);
    bool delete_edge(const Name& start,const Name& end);

    bool delete_edge(Vertex* start, Vertex* end) {
         return delete_edge(start->get_name(), end->get_name());
    }

    Vertices_Range vertices() const { return make_pair(begin(),end()); }

    size_t vertices_count() const { return vertices_map.size(); }
    size_t edge_count() const { return edges_count; }

    Vertex* get_vertex(const Name& n) {
        if (vertices_map.find(n) == vertices_map.end()) { return NULL; }
        return vertices_map[n];
    }

    Edge* get_edge(const Name& n1, const Name& n2) {
        bool b = vertices_map.find(n1) == vertices_map.end();
        if (b) { return NULL; }

        b = vertices_map[n1]->out_edges.find(vertices_map[n2]) == vertices_map[n1]->out_edges.end();
        if (b) { return NULL; }

        return vertices_map[n1]->out_edges[vertices_map[n2]];
    }

    Edge* get_edge(Vertex* n1, Vertex* n2) {
        return get_edge(n1->get_name(), n2->get_name());
    }

    Vertex* Bellman_Ford(Vertex* s);

    BiGraph* getMinSpanningTree();

    void init();

    void DFS(Name start) {
        init();
        Vertex* strt = get_vertex(start);
        strt->colour = GRAY;
        DFS_visit(strt);
        strt->colour = BLACK;
        for (Vertex_Iterator i = begin(); i != end(); ++i){
            if (i->colour == WHITE) {
                i->colour= GRAY;
                DFS_visit(&(*i));
                i->colour = BLACK;
            }
        }
    }

  private:
    map<Name,Vertex*> vertices_map;
    size_t edges_count;
    bool orient;

    Vertex* find_or_create_vertex(const Name &v);

    void DFS_visit(Vertex* v) {
        for (Out_Edge_Iterator i = v->out_edge_begin(); i != v->out_edge_end(); ++i) {
            Vertex* u = (i->get_vertices()).second;
            if (u->colour == WHITE) {
                u->colour = GRAY;
                u->parent = v;
                DFS_visit(u);
                u->colour = BLACK;
            }
        }
    }

};



template <typename T>
typename BiGraph<T>::Edge* BiGraph<T>::add_edge(const T &start,const T & end, double weight){
    if (start==end) {
        add_vertex(start);
        return 0;
    }

    Vertex* start_vertex = find_or_create_vertex(start);
    Vertex* end_vertex = find_or_create_vertex(end);

    map_VE_It existing_edge=start_vertex->out_edges.find(end_vertex);

    if ( existing_edge!=start_vertex->out_edges.end()){
        return existing_edge->second;
    }
    Edge* new_edge = new Edge(start_vertex, end_vertex, weight);
    start_vertex->out_edges.insert(make_pair(end_vertex, new_edge));
    end_vertex->in_edges.insert(make_pair(start_vertex, new_edge));

    ++edges_count;

    if (!orient) { add_edge(end, start, weight); }
    return new_edge;
}

template <typename T>
bool BiGraph<T>::delete_edge(const T& start, const T& end){
    if (vertices_map.find(start)==vertices_map.end()) { return false; }
    if (vertices_map.find(end)==vertices_map.end()) { return false; }

    Vertex* start_vertex = vertices_map[start];
    Vertex* end_vertex = vertices_map[end];
    if ( start_vertex->out_edges.find(end_vertex)==start_vertex->out_edges.end()) { return false; }
    start_vertex->out_edges.erase(end_vertex);
    delete end_vertex->in_edges[start_vertex];
    end_vertex-> in_edges.erase(start_vertex);

    --edges_count;
    if (!orient) { delete_edge(end, start); }
    return true;
}

template <typename T>
pair<bool, typename BiGraph<T>::Vertex*> BiGraph<T>::add_vertex(const T &v){
    if ( vertices_map.find(v)!=vertices_map.end()){return make_pair(false, vertices_map[v]) ;}
    Vertex* y  = new Vertex(v);
    vertices_map.insert(make_pair(v, y));

    return make_pair(true, y);
}

template <typename T>
void BiGraph<T>::clear(){
    for (map_NV_It i=vertices_map.begin(); i!=vertices_map.end();++i){
        for (Out_Edge_Iterator y = i->second->out_edge_begin(); y!=i->second->out_edge_end(); ++y) { delete &(*y); }
        delete i->second;
    }
    vertices_map.clear();
}

template <typename T>
typename BiGraph<T>::Vertex* BiGraph<T>::find_or_create_vertex(const T &v){
    if (vertices_map.find(v)==vertices_map.end()) {
        Vertex* new_vertex = new Vertex(v);
        vertices_map.insert(make_pair(v, new_vertex));
        return new_vertex;
    }
    return vertices_map[v];
}

template <typename T>
void BiGraph<T>::init() {
    for( Vertex_Iterator i=begin(); i!= end(); ++i){
        i->cost = std::numeric_limits<double>::infinity();
        i->parent = NULL;
        i->closed = false;
        i->colour = WHITE;
    }
}

template <typename T>
BiGraph<T>* BiGraph<T>::getMinSpanningTree() {
    if (orient) { return NULL; }
    init();
    BiGraph<T>* result = new BiGraph(false);
    Vertex* start = &(*begin());
    if ( start == NULL ) { return NULL; }
    start->cost = 0;

    std::multimap<double, Vertex*> queue;
    for (Vertex_Iterator i = begin(); i!= end(); ++i){
        queue.insert(make_pair(i->cost, &(*i)));
    }

    Vertex* v;
    Vertex* u;

    while (!queue.empty()){
        v = queue.begin()->second;
        queue.erase(queue.begin());
        v->closed = true;

        for (Out_Edge_Iterator i = v->out_edge_begin(); i != v->out_edge_end(); ++i) {
            u = (i->get_vertices()).second;
            if (u->closed) { continue; }

            typename std::multimap<double, Vertex*>::iterator low = queue.lower_bound(u->cost);
            typename std::multimap<double, Vertex*>::iterator up = queue.upper_bound(u->cost);

            for (; low != up; ++low ) {
                if (low->second == u) { break; }
            }

            if (i->weight < u->cost) {
                queue.erase(low);
                u->cost = i->weight;
                u->parent = v;
                queue.insert(make_pair(i->weight, u));
            }

        }

        if (v->parent && v) {
            double w = get_edge(v->parent->get_name(), v->get_name())->weight;
            result->add_edge(v->parent->get_name(), v->get_name(), w);
        }
    }

    return result;
}
